#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 定义方向数组，用于表示上下左右四个方向
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

// 定义状态结构体，用于存储当前的血量、位置和攻击力
struct State {
    int hp;
    int x, y;
    int attack;
    // 重载小于运算符，用于优先队列的比较
    bool operator<(const State& other) const {
        return hp > other.hp;
    }
};

// 计算击败怪物所需的最少血量
int calculateMinHp(int playerAtk, int monsterAtk, int monsterHp) {
    int turns = (monsterHp + playerAtk - 1) / playerAtk;
    int damage = (turns - 1) * monsterAtk;
    return damage + 1;
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        int n, m, A;
        cin >> n >> m >> A;
        vector<string> grid(n);
        for (int i = 0; i < n; ++i) {
            cin >> grid[i];
        }
        vector<pair<int, int>> monsters;
        int startX, startY, endX, endY, blessingX, blessingY;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '#') {
                    monsters.emplace_back(i, j);
                } else if (grid[i][j] == 'S') {
                    startX = i;
                    startY = j;
                } else if (grid[i][j] == 'T') {
                    endX = i;
                    endY = j;
                } else if (grid[i][j] == '!') {
                    blessingX = i;
                    blessingY = j;
                }
            }
        }
        vector<pair<int, int>> monsterStats(m + 1);
        for (int i = 0; i < m + 1; ++i) {
            cin >> monsterStats[i].first >> monsterStats[i].second;
        }
        // 三维数组用于记录到达每个位置、每个攻击力下的最小血量
        vector<vector<vector<int>>> dist(n, vector<vector<int>>(n, vector<int>(2 * A + 1, INT_MAX)));
        priority_queue<State> pq;
        pq.push({1, startX, startY, A});
        dist[startX][startY][A] = 1;
        while (!pq.empty()) {
            State cur = pq.top();
            pq.pop();
            int curHp = cur.hp;
            int curX = cur.x;
            int curY = cur.y;
            int curAtk = cur.attack;
            if (curHp > dist[curX][curY][curAtk]) continue;
            if (curX == endX && curY == endY) {
                cout << curHp << endl;
                return 0;
            }
            for (int k = 0; k < 4; ++k) {
                int newX = curX + dx[k];
                int newY = curY + dy[k];
                if (newX >= 0 && newX < n && newY >= 0 && newY < n) {
                    int newHp = curHp;
                    int newAtk = curAtk;
                    if (grid[newX][newY] == '.') {
                        // 空格子，血量和攻击力不变
                        newHp = curHp;
                        newAtk = curAtk;
                    } else if (grid[newX][newY] == '!') {
                        // 祝福点，攻击力增加 A
                        newAtk = curAtk + A;
                    } else if (grid[newX][newY] == '#') {
                        // 小怪
                        int monsterIndex = -1;
                        for (int i = 0; i < monsters.size(); ++i) {
                            if (monsters[i].first == newX && monsters[i].second == newY) {
                                monsterIndex = i;
                                break;
                            }
                        }
                        int monsterAtk = monsterStats[monsterIndex].first;
                        int monsterHp = monsterStats[monsterIndex].second;
                        int minHp = calculateMinHp(curAtk, monsterAtk, monsterHp);
                        newHp = max(curHp, minHp);
                    } else if (grid[newX][newY] == 'T') {
                        // Boss
                        int monsterAtk = monsterStats[m].first;
                        int monsterHp = monsterStats[m].second;
                        int minHp = calculateMinHp(curAtk, monsterAtk, monsterHp);
                        newHp = max(curHp, minHp);
                    }
                    if (newHp < dist[newX][newY][newAtk]) {
                        dist[newX][newY][newAtk] = newHp;
                        pq.push({newHp, newX, newY, newAtk});
                    }
                }
            }
        }